package 牛客.字符串;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

/*
    给出一个仅包含字符'(',')','{','}','['和']',的字符串，判断给出的字符串是否是合法的括号序列
    括号必须以正确的顺序关闭，"()"和"()[]{}"都是合法的括号序列，但"(]"和"([)]"不合法。
    示例1    输入 "["     返回值 false
    示例2    输入 "[]"    返回值true
 */
public class 括号序列 {
    public boolean isValid (String s) {
        char[] str = s.toCharArray();
        Deque<Character> deque = new LinkedList<>();
        for (int i = 0; i < str.length; i++) {
            if (str[i] == '{' || str[i] == '[' || str[i] == '(') {
                deque.push(str[i]);
                continue;
            }
            else if (str[i] == '}' && !deque.isEmpty()) {
                if (deque.peek() == '{') {
                    deque.pop();
                    continue;
                } else {
                    return false;
                }
            }
            else if (str[i] == ']' && !deque.isEmpty()) {
                if (deque.peek() == '[') {
                    deque.pop();
                    continue;
                } else {
                    return false;
                }
            }
            else if (str[i] == ')' && !deque.isEmpty()) {
                if (deque.peek() == '(') {
                    deque.pop();
                    continue;
                } else {
                    return false;
                }
            }
            else if(deque.isEmpty()) return false; //有可能左括号少
        }
            if (deque.isEmpty())
                return true;
            else
                return false;
    }

    public static void main(String[] args) {
        String s = ")";
        括号序列 obj = new 括号序列();
        System.out.println(obj.isValid(s));
    }
}
